1. Field of the Invention
The present invention relates to a method for optimizing a cell allocation using the Min-cut method in the design system of LSI and its apparatus.
2. Description of the Related Art
For example, in LSI designing using a computer for a logic design, firstly, cells of logic elements such as AND and OR gates, and how to interconnect these cells (called a "net") are decided. Secondly, how to position cells on a chip is decided. Lastly, how to spread the net among the cells.
The Min-cut method is often used in cell allocation. FIGS. 1A and 1B show the Min-cut method. In the figures, 100 indicates an LSI block in which cells are allocated, 110 to 114 cells, 120 a net not cut, 121 a cut, and 130 and 131 cut lines for dividing a block respectively.
In the conventional Min-cut method cell allocation block of LSI 100 is divided into several blocks, and Cells 110 to 114 are allocated to each block. In this case there is a division into two blocks horizontally or vertically as shown in FIG. 1A, one into four blocks horizontally and vertically at the same time as shown in FIG. 1B and one into more blocks for this dividing method.
At this time the following conditions shall be satisfied.
a) The total of cell areas to be allocated to each block shall satisfy certain restriction requirements. In the case of a division into two blocks, for example, the following equation shall be satisfied for a constant .epsilon. which is more than 0. EQU .vertline.S.sub.1 /A.sub.1 -S.sub.2 /A.sub.2 .vertline.&lt;.epsilon.
where
S.sub.1 : Total of cell areas allocated to Block 1 PA1 A.sub.1 : Area of Block 1 PA1 S.sub.2 : Total of cell areas allocated to Block 2 PA1 A.sub.2 : Area of Block 2
b) When a cell connected to a certain net is allocated to another block, a net crossing a line dividing a block (cut line) (the net is called a "cut") is generated. Cells shall be allocated to each block so that the number of its cuts may be reduced as much as possible. A method can also be used for minimizing a cost function which is generated by attaching weight W.sub.i to net i and taking the sum total of weight W.sub.i of nets crossing a cut line.
There are various methods for obtaining such a division so as to minimize the cost function including the Fidducia-Matteyses(FM) method. Here, we shall call these requirements for optimizing a cell allocation, as mentioned in a) and b), "optimizing requirements."
FIG. 2 shows the conventional method for obtaining such a division so as to minimize a cost function.
As shown in FIG. 2 a system for obtaining such a division so as to minimize a cost function is provided with cell area restriction requirements judging module 150 for judging whether or not its pattern satisfies its cell area restriction using a cell dividing pattern as an input, and cost function calculating module 160 for outputting a cost function for the pattern using a cell dividing pattern as an input, and it is structured so that a dividing pattern for giving the minimum cost function may be obtained under the restriction requirements while optimization module 140 is calling up both modules.
In its actual implementation it is designed so that its area restriction and cost function change can be output as a result of using a difference from the current dividing pattern (for example, information of "cell A moves from Block 1 to Block 2" as an input.
FIG. 3 shows a cell position deciding method by the conventional Min-cut method. After Block 100 is divided by cut line 130, each block is divided again in the same way. When the block size is reduced sufficiently by repeating divisions such as a division by cut line 131, a division by cut lines 132 and 133, and further, a division by cut lines 134 and 135, its cell position is decided by the module shown in FIG. 2.
Why the number of its cuts is minimized is because it is anticipated that the density of a net is reduced and its routing becomes easy.
However, because in the conventional Min-cut method how to arrange the cut made by the current division by means of a cut line was not taken into consideration, as a result there was a possibility that the number of its cuts might be unbalanced on the boundary of each block.
FIGS. 4A and 4B show when, in the conventional Min-cut method, the existing cuts become unbalanced by the current cut line.
Here, the state where a division is made again after the first division is assumed. As shown in FIG. 4A it is assumed that the number of its cuts is 100 when, first, a division is made vertically by vertical cut line 130. Next, as shown in FIG. 4B, a division is made horizontally by horizontal cut line 131. At this time when cells connected to all the first 100 pieces of cuts are allocated to its upper half, the density of the upper half becomes higher than its lower half and its routing becomes difficult to make.
As in the conventional Min-cut method, one part with a high net density and one with a low net density are generated and their routing density often becomes unbalanced. Therefore, a cell allocation most suitable for its routing could not necessarily be obtained.